package leetcode.秋招.腾讯.第二次;

import leetcode.util.CommonUtils;
import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    @Test
    public void test() {
        TreeNode root = new TreeNode(1, new TreeNode(10, new TreeNode(7, new TreeNode(5), new TreeNode(4, new TreeNode(8), new TreeNode(3, new TreeNode(6), null))), new TreeNode(9))
                , new TreeNode(2));
        CommonUtils.printTreeNodeByLayer(root);
        solve(root, new int[][]{{8, 3}, {5, 6}, {4, 5}, {2, 7}});
        CommonUtils.printTreeNodeByLayer(root);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param root TreeNode类 指向量子树的根
     * @param b int整型二维数组 表示每次交换的两个子树
     * @return TreeNode类
     */
    public TreeNode solve (TreeNode root, int[][] b) {
        // write code here
        if (root == null) return root;
        for (int[] nums : b) {
            int x = nums[0];
            int y = nums[1];
            if (x == root.val || y == root.val) continue;
            TreeNode fx = getTreeNode(root, x);
            TreeNode temp;
            if (fx.left != null && fx.left.val == x) {
                temp = fx.left;
            } else
                temp = fx.right;
            TreeNode fy = getTreeNode(root, y);
            if (isP(temp, fy.val)) continue;
            if (fx.left.val == x && fy.left.val == y) {
                TreeNode tmp = fx.left;
                fx.left = fy.left;
                fy.left = tmp;
            } else if (fx.left.val == x && fy.right.val == y) {
                TreeNode tmp = fx.left;
                fx.left = fy.right;
                fy.right = tmp;
            } else if (fx.right.val == x && fy.left.val == y) {
                TreeNode tmp = fx.right;
                fx.right = fy.left;
                fy.left = tmp;
            } else {
                TreeNode tmp = fx.right;
                fx.right = fy.right;
                fy.right = tmp;
            }
        }
        return root;
    }

    private boolean isP(TreeNode fx, int fy) {
        if (fx == null) return false;
        if ((fx.left != null && fx.left.val == fy)
                || (fx.right != null && fx.right.val == fy)) return true;
        return isP(fx.left, fy) || isP(fx.right, fy);
    }

    TreeNode getTreeNode(TreeNode root, int num) {
        if (root == null) return null;
        if ((root.left != null && root.left.val == num) || (root.right != null && root.right.val == num)) return root;
        TreeNode temp = getTreeNode(root.left, num);
        if (temp != null) return temp;
        else return getTreeNode(root.right, num);
    }
}